#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef struct node
{
	int data;
	struct node *left,*right;
}*tree;
bool judge(tree a,tree b)  //判断两棵子树是否对称
{
	if(a==NULL&&b==NULL) //a,b都为空，对称
		return true;
	else if(a==NULL||b==NULL) //一个空，一个不空，不对称
		return false;
	else if(a->data!=b->data)//都不为空，但左右不等,不对称
		return false;
	else  //都不为空，如果相等，递归判断a的左子树与b的右子树，及a的右子树与b的左子树
		return judge(a->left,b->right)&&judge(a->right,b->left);
}
bool fun(tree root)//判断二叉树是否对称
{
	if(root==NULL)
		return true;
	return judge(root->left,root->right);//递归判断左右子树
}
tree newNode(int data){
	tree node=(tree)malloc(sizeof(struct node));
	node->data=data;
	node->left=NULL;
	node->right=NULL;
	return node;
}
tree create(tree root,int data){
	if(root==NULL)
		return newNode(data);
	if(root->data>data)
		root->left=create(root->left,data);
	else
		root->right=create(root->right,data);
	return root;
}
void preOrder(tree root){
	if(NULL==root)
		return;
	stack<tree> nodeStack;
	nodeStack.push(root);
	while(!nodeStack.empty()){
		tree p=nodeStack.top();
		printf("%d ",p->data);
		nodeStack.pop();
		if(p->right)nodeStack.push(p->right);
		if(p->left)nodeStack.push(p->left);
	}
}
int main(){
	tree root=NULL;
	int arr[7]={40,30,30,10,10,60,60};
	for(int i=0;i<7;i++){
		root=create(root,arr[i]);
	}
	preOrder(root);
	printf("\n%d",fun(root));
	return 0;
}
